//给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
//
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//
// 示例 1：
//
//
//输入：k = 2, prices = [2,4,1]
//输出：2
//解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
//
// 示例 2：
//
//
//输入：k = 2, prices = [3,2,6,5,0,3]
//输出：7
//解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
//     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3
//。
//
//
//
// 提示：
//
//
// 0 <= k <= 100
// 0 <= prices.length <= 1000
// 0 <= prices[i] <= 1000
//
//
// Related Topics 数组与矩阵 动态规划 👍 946 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function maxProfit(k: number, prices: number[]): number {

    /*?
        ? dp[i][1] 持有   dp[i][1] = dp[i - 1][1], dp[i - 1][2] - prices[i]
        ? dp[i][2] 未持有  dp[i][2] = dp[i - 1][2], dp[i - 1][1] + prices[i]
        ? dp的第二个索引为偶数时卖出 奇数时买入
    ?*/

    const dp: number[][] = new Array(prices.length).fill(0).map(_ => new Array(k * 2 + 1).fill(0));
    //? 初始状态 k天买入都置为-prices[0]
    for (let i = 1; i <= k; i++) {
        dp[0][i * 2 - 1] = -prices[0];
    }
    for (let i = 1; i < prices.length; i++) {  //? 遍历天数
        for (let j = 1; j < 2 * k + 1; j++) { //? 遍历情况
            //? Math.pow(-1, j)根据j的奇偶性决定是买（奇）还是卖（偶）
            //? 不管是买还是卖，沿用前一天状态均为dp[i - 1][j]  第i天买/卖操作了 dp[i-1][j-1]代表前一天状态j-1（持有或不持有股票）的最大现金 再加/减当前值
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + Math.pow(-1, j) * prices[i]);
        }
    }
    return dp[dp.length - 1][2 * k];
};
//leetcode submit region end(Prohibit modification and deletion)
